353. Design Snake Game
Medium

Design a Snake game that is played on a device with screen size height x width. Play the game online if you are not familiar with the game.

The snake is initially positioned at the top left corner (0, 0) with a length of 1 unit.

You are given an array food where food[i] = (ri, ci) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game's score both increase by 1.

Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.

When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).

Implement the SnakeGame class:

  • SnakeGame(int width, int height, int[][] food) Initializes the object with a screen of size height x width and the positions of the food.
  • int move(String direction) Returns the score of the game after applying one direction move by the snake. If the game is over, return -1.

 

Example 1:

Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]

Explanation
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // return 0
snakeGame.move("D"); // return 0
snakeGame.move("R"); // return 1, snake eats the first piece of food. The second piece of food appears
                     // at (0, 1).
snakeGame.move("U"); // return 1
snakeGame.move("L"); // return 2, snake eats the second food. No more food appears.
snakeGame.move("U"); // return -1, game over because snake collides with border

 

Constraints:

  • 1 <= width, height <= 104
  • 1 <= food.length <= 50
  • food[i].length == 2
  • 0 <= ri < height
  • 0 <= ci < width
  • direction.length == 1
  • direction is 'U', 'D', 'L', or 'R'.
  • At most 104 calls will be made to move.
Accepted
47,780
Submissions
130,892
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.33 (12 votes)

Premium

Solution


Overview

Who doesn't feel nostalgic while thinking about the famous Snake video game? It used to be (and still is) the goto video game on phones and other platforms for so many of us and there are countless variations of the game out there. The version that this problem talks about is the most basic one. And this being a design problem makes things more interesting!

Let's go over the details in the problem statement once.

  • We're given the width and height of the grid over which the snake moves.
  • Additionally, we are also given the list of grid positions where the food would appear one after the other. Just like the traditional snake, the next food item only appears once the current one is consumed.
  • Consuming a piece of food increasses the length of the snake by one. In terms of our problem statement, the length of the snake is increased by one more cell from the grid with each cell being of unit length and width.
  • The snake can move in four directions U, D, L, and R. Everytime the snake has to be moved, the move() function would be called and this is the only function we need to focus on in this question.
  • The game ends when either of these conditions happens:
    • The snake becomes too long to potentially fit inside the grid or
    • The snake hits one of the boundaries which would happen in the previous case as well.
    • The snake bites itself i.e. when the head of the snake collides with its body in the next move.

The problem statement doesn't have any follow up statements, but we're going to discuss a follow-up to this question where the wall becomes infinite i.e. the snake can move across walls and the only condition then for the game to end is when the snake crashes into itself on the grid.


Approach: Queue and Hash Set

Intuition

Let's start by thinking about how we want to store the snake?

In terms of the grid, a snake is just an ordered collection of cells.

We can technically use an array to store the cells representing a snake. However, we would need to instantiate an array the size of width * height of the grid since a snake can be composed of all the the cells of the grid in the worst case. A spiral kind of a snake. Let's look at such a snake occupying the grid.

This structure is highly unlikely given the random nature of food items appearing on the grid. However, we would need an array the size of the grid to be able to hold this big a snake. The breaking point for an array is when we have to move the snake from one position to another. Let's see what happens to the snake when it moves by one in a direction. The result overall would be the same with some minor changes based on the direction.

In the above figure, we have a snake that occupies 4 cells across the grid or in other words, is of length 4. The snake can be represented by the following collection of cells: [(1,1), (1,2), (1,3), (2,3)]. Now say we have the snake move in the right direction i.e. R. The snake now would look like this across the grid.

Now here, after moving one step to the right, the snake is represented by the cells [(1,2), (1,3), (2,3), (2,4)].

In order to achieve this with an array, we would have to move all the cells around per move which is not exactly ideal. We can build some complicated logic around the movement of the snake in an array but that won't be worth the fixed space complexity that an array would occupy.

Let's see what data structure would naturally fit our requirements for the snake. There are two basic requirements we need to satisfy:

  1. Dynamically add new cells to the snake's body and
  2. Move the snake in constant amount of time across the grid.

Let's look at the snake representation between moves from the example above to understand what really is happening here and that will help us get to the data structure we need to use for solving this problem.

Move with No Food

We already have an example for such a move so we will simply be looking at the snake representation on the grid to understand what's really happening here.

Before the move, the snake was occupying the following cells of the grid in the specified order:

(1,1), (1,2), (1,3), (2,3)

and after the move, the snake was occupying the following positions on the grid:

(1,2), (1,3), (2,3), (2,4)

If you think about this from a sliding window perspective, we simply moves the window one step forward i.e. we removed the tail of the window and added a new head to the window. The tail in this case was (1,2) and the new head being (2,4).

Move with Food Consumption

Now let's look at a move by the snake wherein they consume a food item and grow in length. Suppose the move was the same as before and the spot (2,4) contained a food item. The snake head from the previous example, was at (2,3) on the grid. So, a move to the right would cause them to consume this food item thus extending their overall length by one. So now, instead of occupying 4 cells on the grid, the snake would occupy 5 cells. Let's concretely look at the snake representations before and after the move.

Before the move, the snake was occupying the following cells of the grid in the specified order:

(1,1), (1,2), (1,3), (2,3)

and after the move, the snake was occupying the following positions on the grid:

(1,1), (1,2), (1,3), (2,3), (2,4)

Here, we simply added a new head to the snake with the head being the cell (2,4). The tail remained the same in this case. These are the only two possibilities for moves that can happen other than the termination conditions for the game. Based on them, let's see what operations out data structure needs to support concretely for us to be able to perform these moves efficiently.

Our abstract data structure needs to support the following operations efficiently.

  1. Grow in size dynamically. Note that we never shrink in size. The snake can stay the same size as before or grow in size due to the consumption of a food item on the grid. But they can't shrink in size.
  2. Maintain a specified ordering of cells in order to represent the snake.
  3. Extract the tail cell and potentially add a new head cell to the ordering of cells to represent the updated snake post a move. This is the most important operation of all and this points to a very specific data structure.

Based on the third operation, we can see that the Queue would be a good data structure to use since we need to have quick access to the first and last elements of an ordered list and a queue gives us exactly that.

A queue is an abstract data structure with some specified properties which meets our requirements. It can be represented by an array or a linked list. For our purposes, since we need a data structure with dynamic sizing, we would go with a linked-list based implementation for a queue rather than an array since we don't want to pre-allocate any memory for the array and only allocate on the fly. A linked list would be a great fit here since we don't require random access to cells of the snake.

Algorithm

  1. Initialize a queue containing a single cell (0,0) which is the initial position of the snake at the beginning of the game. Note that we will be doing this in the constructor of the class and not in the move function.

  2. The fist thing we need to do inside the move function is to compute the new head based on the direction of the move. As we saw in the intuition section, irrespective of the kind of move, we will always get a new head. We need the new head position to determine if the snake has hit a boundary and hence, terminate the game.

  3. Let's first discuss the termination conditions before moving on to the modifications we would make to our queue data structure.

    1. The first condition is if the snake cross either of the boundaries of the grid after the mode, then we terminate. So for this, we simply check if the new head (new_head) satisfies new_head[0] < 0 or new_head[0] > height or new_head[1] < 0 or new_head[1] > width.
    2. The second condition is if the snake bites itself after the move. An important thing to remember here is that the current tail of the snake is not a part of the snake's body. If the move doesn't involve a food, then the tail gets updated (removed) as we have seen. If this is a food move, then the snake cannot bite itself because the food cannot appear on any of the cells occupied by the snake (according to the problem statement).

    In order to check if the snake bites itself we need to check if the new head already exists in our queue or not. This can turn out to be an O(N)\mathcal{O}(N) operation and that would be costly. So, at the expense of memory, we can also use an additional dictionary data structure to keep the positions of the snake. This dictionary will only be used for this particular check. We can't do with just a dictionary because a dictionary doesn't have an ordered list of elements and we need the ordering for our implementation.

  4. If none of the termination conditions have been met, then we will continue to update our queue with the new head and potentially remove the old tail. If the new head lands on a position which contains food, then we simply add the new head to our queue representing the snake. We won't pop the tail in this case since the length of the snake has increased by 1.

  5. After each move, we return the length of the snake if this was a valid move. Else, we return -1 to indicate that the game is over.

Complexity Analysis

Let WW represent the width of the grid and HH represent the height of the grid. Also, let NN represent the number of food items in the list.

  • Time Complexity:
    • The time complexity of the move function is O(1)\mathcal{O}(1).
    • The time taken to calculate bites_itself is constant since we are using a dictionary to search for the element.
    • The time taken to add and remove an element from the queue is also constant.
  • Space Complexity:
    • The space complexity is O(W×H+N)\mathcal{O}(W \times H + N)
    • O(N)\mathcal{O}(N) is used by the food data structure.
    • O(W×H)\mathcal{O}(W \times H) is used by the snake and the snake_set data structures. At most, we can have snake that occupies all the cells of the grid as explained in the beginning of the article.

Report Article Issue

Comments: 8
rsfrost's avatar
Read More

You could just use a set for checking if the snake bites itself Instead of a dictionary.

9
Show 1 reply
Reply
Share
Report
json_read's avatar
Read More

Has to be HARD difficulty isnt it?

29
Show 5 replies
Reply
Share
Report
Endianless's avatar
Read More

This isn't very hard if you just start to do it and live with the fact that you need half a dozen class vars. One disappointment is in AC and test case it expects snake to move its tail first then the head, which is not how nature works and actually produces more corner cases this way.

class SnakeGame {

    private final int W;
    private final int H;
    private final Map<String, int[]> dir = new HashMap<>();
    private final int[][] food;
    private int currFood = 0;
    private int score = 0;
    private final Deque<Integer> queue = new LinkedList<>();
    private final Set<Integer> snake = new HashSet<>();
    private int r = 0;
    private int c = 0;
    
    /** Initialize your data structure here.
        @param width - screen width
        @param height - screen height 
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
    public SnakeGame(int width, int height, int[][] food) {
        W = width;
        H = height;
        this.food = food;
        
        dir.put("U", new int[] {-1,0});
        dir.put("D", new int[] {1,0});
        dir.put("L", new int[] {0,-1});
        dir.put("R", new int[] {0,1});
        
        queue.add(0);
        snake.add(0);
    }
    
    /** Moves the snake.
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 
        @return The game's score after the move. Return -1 if game over. 
        Game over when snake crosses the screen boundary or bites its body. */
    public int move(String direction) {
        int[] d = dir.get(direction);
        r += d[0];
        c += d[1];
        if (r < 0 || r == H || c < 0 || c == W) return -1;
        
        int hash = r * 100000 + c;
                
        // there is an ambiguity should the tail move first or the head move first
        // by observing nature the head should that it can eat its tail
        // but test case says tail move first, that produces more "corner cases" like duplicated hash
        if (snake.contains(hash) && hash != queue.peekLast()) return -1;
        
        if (currFood < food.length && r == food[currFood][0] && c == food[currFood][1]) {
            score++;
            currFood++;
        } else {
            snake.remove(queue.removeLast());
        }
        
        // head can occupy previous tail location, remove tail then add head
        queue.addFirst(hash);
        snake.add(hash);
        
        return score;
    }
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame obj = new SnakeGame(width, height, food);
 * int param_1 = obj.move(direction);
 */

1
Reply
Share
Report
Xyzzy123's avatar
Read More

An observation: The problem description provides these constraints:

1 <= width, height <= 10^4
1 <= food.length <= 50

The maximum amount of food is tiny. Given this, the snake can never be longer than 51 segments. As a consequence:

(1) The snake does not require O(W * H) memory. That would mean a potential worst case of O(10^4 x 10^ 4) = O(100,000,000) memory. (In some languages, like Python this might require 1GB of RAM or more, given the overhead with objects and arrays!)

Instead, it requires O(f) memory, where f is the amount of food. For practical purposes, this is equivalent to O(1) memory.

(2) For similar reasons, there isn't a Big-O performance benefit from using a separate hash set to store the snake's segment positions. In Python, you can simply iterate over the deque -- which contains at most O(51) segments -- to check for collisions. This simplifies the code substantially and eliminates a class variable:

        # Have we collided with the tail?
        if (row, col) in self.snake:
            return -1

(In other languages, this might be more difficult, but not impossible.)

Using a hash set might be an optimization, but it doesn't provide a meaningful Big-O improvement in performance. In practice, I had exactly the same timings on LeetCode (240ms) for both approaches.

You can also simplify the code further by reversing the food list and storing it as a stack. Then, when the snake consumes food, you can pop that food item off the stack.

My complete code is below:

class SnakeGame:

    def __init__(self, width: int, height: int, food: List[List[int]]):
        self.snake = collections.deque([(0, 0)])
        self.food = list(reversed(food))
        self.width = width
        self.height = height
        self.directions = {
            "U": (-1, 0),
            "D": (1, 0),
            "L": (0, -1),
            "R": (0, 1)
        }

    def move(self, direction: str) -> int:
        
        # Get new coordinates of snake head
        drow, dcol = self.directions[direction]
        row, col = self.snake[-1][0] + drow, self.snake[-1][1] + dcol
        
        # Are we out of bounds?
        if not (0 <= row < self.height and 0 <= col < self.width):
            return -1

        # Is there food at this position?
        if self.food and row == self.food[-1][0] and col == self.food[-1][1]:  
            self.food.pop()                # Consume the food
        else:
            tail = self.snake.popleft()    # Contract the tail by one segment
        
        # Have we collided with the tail?
        if (row, col) in self.snake:
            return -1
        
        # Advance the head
        self.snake.append((row, col))
        
        # Return the current score
        return len(self.snake) - 1

0
Reply
Share
Report
rthota50's avatar
Read More

I am not seeing any need for snake HashMap<Pair<>>, HashSet<Pair<>> should be good enough? Am I missing something. Is Pair<> not compatible with HashSet?

0
Reply
Share
Report
Sleuther56's avatar
Read More

not only are companies asking algo bs, we have to learn this? I think this is more practical than doing binary tree problems .

0
Show 1 reply
Reply
Share
Report
yh32's avatar
Read More

How could you use Pair class in hash without overriding the equal() and hashCode()?

0
Show 1 reply
Reply
Share
Report
Moo_K's avatar
Read More

I think the space complexity can be summed up by O(N), because as you mentioned, the worst case scenario is the body of the snake filling every single tile given by the width and height. However, you need food to make the snake grow, and if the snake filled the tiles, it will be O(3N), 1N for food structure, 1N for snake body in deque, and 1N for the set containing the indices.

0
Reply
Share
Report

You don't have any submissions yet.

353/1883
Contribute
|||
Saved
#351 Android Unlock Patterns
Medium
#352 Data Stream as Disjoint Intervals
Hard
#353 Design Snake Game
Medium
#354 Russian Doll Envelopes
Hard
#355 Design Twitter
Medium
#356 Line Reflection
Medium
#357 Count Numbers with Unique Digits
Medium
#358 Rearrange String k Distance Apart
Hard
#359 Logger Rate Limiter
Easy
#360 Sort Transformed Array
Medium
#361 Bomb Enemy
Medium
#362 Design Hit Counter
Medium
#363 Max Sum of Rectangle No Larger Than K
Hard
#364 Nested List Weight Sum II
Medium
#365 Water and Jug Problem
Medium
#366 Find Leaves of Binary Tree
Medium
#367 Valid Perfect Square
Easy
#368 Largest Divisible Subset
Medium
#369 Plus One Linked List
Medium
#370 Range Addition
Medium
#371 Sum of Two Integers
Medium
#372 Super Pow
Medium
#373 Find K Pairs with Smallest Sums
Medium
#374 Guess Number Higher or Lower
Easy
#375 Guess Number Higher or Lower II
Medium
#376 Wiggle Subsequence
Medium
#377 Combination Sum IV
Medium
#378 Kth Smallest Element in a Sorted Matrix
Medium
#379 Design Phone Directory
Medium
#380 Insert Delete GetRandom O(1)
Medium
#381 Insert Delete GetRandom O(1) - Duplicates allowed
Hard
#382 Linked List Random Node
Medium
#383 Ransom Note
Easy
#384 Shuffle an Array
Medium
#385 Mini Parser
Medium
#386 Lexicographical Numbers
Medium
#387 First Unique Character in a String
Easy
#388 Longest Absolute File Path
Medium
#389 Find the Difference
Easy
#390 Elimination Game
Medium
#391 Perfect Rectangle
Hard
#392 Is Subsequence
Easy
#393 UTF-8 Validation
Medium
#394 Decode String
Medium
#395 Longest Substring with At Least K Repeating Characters
Medium
#396 Rotate Function
Medium
#397 Integer Replacement
Medium
#398 Random Pick Index
Medium
#399 Evaluate Division
Medium
#400 Nth Digit
Medium